Fractional Knapsack Problem using Greedy Approach
The core of the Fractional Knapsack problem lies in the concept of
maximizing the total value by selecting items with varying weights and values, such that they
fit within a given capacity constraint. Unlike the traditional Knapsack problem, the Fractional
Knapsack problem allows us to take fractions of items.
This technique is commonly applied in
resource allocation scenarios, where the goal is to optimize profit or efficiency under certain
limits.
Video Lecture
Problem
Given a set of items, each with a weight and value, the goal is to maximize the total value by
selecting items (or parts of them) that fit into a knapsack of a fixed capacity. The greedy
approach is employed to achieve an optimal solution, which involves selecting the items with the
highest value-to-weight ratio first.
The process of selecting items based on their ratios is
known as greedy selection.
Input
Given a set of items, each with a weight and value, along with the capacity of the knapsack.
Output
The maximum value that can be obtained by selecting fractions of items.
Example:
- Item 1: Weight = 10, Value = 60
- Item 2: Weight = 20, Value = 100
- Item 3: Weight = 30, Value = 120
Capacity of the knapsack: 50
Types of Knapsack Problems
1. Fractional Knapsack
In this version of the problem, we are allowed to take fractions of items, meaning that even if
an item doesn't completely fit into the knapsack, we can take a fraction of it to maximize the
total value.
2. 0/1 Knapsack
In contrast to the fractional knapsack, in this problem, we are restricted to either taking the
whole item or leaving it. No fractions of items are allowed.
Greedy Approach for Fractional Knapsack
The solution is obtained using the following steps:
- Calculate Value-to-Weight Ratio: For each item, compute the ratio of its
value to its weight.
- Sort Items: Sort the items based on their value-to-weight ratios in
descending order.
- Select Items: Starting from the highest ratio, take as much of each item as
possible, adding fractions if necessary, until the knapsack is full.
Min Heap and Greedy Selection
In the greedy approach, items are sorted based on their value-to-weight ratio. A heap
data structure or simply sorting techniques can be used to manage and select items
efficiently. This ensures that at each step, we are making the most optimal selection for the
current situation.
Problem
Given a set of items, each with a weight and value, the goal is to maximize the total value by
selecting items (or parts of them) that fit into a knapsack of a fixed capacity. The greedy
approach is employed to achieve an optimal solution, which involves selecting the items with the
highest value-to-weight ratio first.
The process of selecting items based on their ratios is
known as greedy selection.
Input
Given a set of items, each with a weight and value, along with the capacity of the knapsack.
Output
The maximum value that can be obtained by selecting fractions of items.
Example:
- Item 1: Weight = 10, Value = 60
- Item 2: Weight = 20, Value = 100
- Item 3: Weight = 30, Value = 120
Capacity of the knapsack: 50
Types of Knapsack Problems
1. Fractional Knapsack
In this version of the problem, we are allowed to take fractions of items, meaning that even if an item doesn't completely fit into the knapsack, we can take a fraction of it to maximize the total value.
2. 0/1 Knapsack
In contrast to the fractional knapsack, in this problem, we are restricted to either taking the whole item or leaving it. No fractions of items are allowed.
Greedy Approach for Fractional Knapsack
The solution is obtained using the following steps:
- Calculate Value-to-Weight Ratio: For each item, compute the ratio of its value to its weight.
- Sort Items: Sort the items based on their value-to-weight ratios in descending order.
- Select Items: Starting from the highest ratio, take as much of each item as possible, adding fractions if necessary, until the knapsack is full.
Min Heap and Greedy Selection
In the greedy approach, items are sorted based on their value-to-weight ratio. A heap data structure or simply sorting techniques can be used to manage and select items efficiently. This ensures that at each step, we are making the most optimal selection for the current situation.
Fractional Knapsack Algorithm (Greedy Approach)
FractionalKnapsack(W, items[0]..items[n-1])
Input: A knapsack with capacity W, and an array items
where each item has a weight and a value.
Output: The maximum total value that can be obtained by filling the knapsack, allowing fractional items.
Step 1: Start.
Step 2: For each item, calculate the value-to-weight ratio
(value/weight).
Step 3: Sort the items in decreasing order of their value-to-weight ratio.
Step 4: Initialize totalValue = 0 and
remainingCapacity = W.
Step 5: For each item in the sorted array, do the following:
Step 6: If the item can fully fit into the remaining capacity, add its full
value to totalValue and subtract its weight from remainingCapacity.
Step 7: If the item cannot fully fit, take a fraction of the item that fits, and
add the corresponding fraction of its value to totalValue.
Step 8: Stop when the knapsack is full or all items have been considered.
Step 9: Output the totalValue.
Step 10: Stop.
Fractional Knapsack Problem using Greedy Approach code
#include <stdio.h>
// Structure to represent an item
struct Item {
int weight;
int value;
};
// Function to swap two items
void swap(struct Item* a, struct Item* b) {
struct Item temp = *a;
*a = *b;
*b = temp;
}
// Function to sort items based on value/weight ratio in descending order
void sortItemsByRatio(struct Item items[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
double r1 = (double)items[j].value / items[j].weight;
double r2 = (double)items[j + 1].value / items[j + 1].weight;
if (r1 < r2) {
swap(&items[j], &items[j + 1]);
}
}
}
}
// Function to calculate maximum value in Knapsack using greedy approach
double knapsackGreedy(struct Item items[], int n, int capacity) {
// Sort items by value/weight ratio
sortItemsByRatio(items, n);
double totalValue = 0.0; // Total value of knapsack
int currentWeight = 0; // Current weight of knapsack
for (int i = 0; i < n; i++) {
if (currentWeight + items[i].weight <= capacity) {
// Take the whole item
currentWeight += items[i].weight;
totalValue += items[i].value;
} else {
// Take the fraction of the remaining item
int remainingCapacity = capacity - currentWeight;
totalValue += (double)items[i].value * ((double)remainingCapacity / items[i].weight);
break; // Knapsack is full
}
}
return totalValue;
}
int main() {
int n, capacity;
// Input number of items
printf("Enter the number of items: ");
scanf("%d", &n);
struct Item items[n];
// Input value and weight of each item
for (int i = 0; i < n; i++) {
printf("Enter value and weight for item %d: ", i + 1);
scanf("%d %d", &items[i].value, &items[i].weight);
}
// Input capacity of knapsack
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
// Calculate maximum value using Greedy algorithm
double maxValue = knapsackGreedy(items, n, capacity);
printf("Maximum value in Knapsack = %.2lf\n", maxValue);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an item
struct Item {
int weight;
int value;
};
// Function to swap two items
void swap(Item& a, Item& b) {
Item temp = a;
a = b;
b = temp;
}
// Function to sort items based on value/weight ratio in descending order
void sortItemsByRatio(vector<Item>& items) {
sort(items.begin(), items.end(), [](Item& a, Item& b) {
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
});
}
// Function to calculate maximum value in Knapsack using greedy approach
double knapsackGreedy(vector<Item>& items, int capacity) {
// Sort items by value/weight ratio
sortItemsByRatio(items);
double totalValue = 0.0;
int currentWeight = 0;
for (Item& item : items) {
if (currentWeight + item.weight <= capacity) {
currentWeight += item.weight;
totalValue += item.value;
} else {
int remainingCapacity = capacity - currentWeight;
totalValue += (double)item.value * ((double)remainingCapacity / item.weight);
break; // Knapsack is full
}
}
return totalValue;
}
int main() {
int n, capacity;
cout < "Enter the number of items: ";
cin >> n;
vector<Item> items(n);
// Input value and weight of each item
for (int i = 0; i < n; i++) {
cout < "Enter value and weight for item " < i + 1 < ": ";
cin >> items[i].value >> items[i].weight;
}
// Input capacity of knapsack
cout < "Enter the capacity of the knapsack: ";
cin >> capacity;
// Calculate maximum value using Greedy algorithm
double maxValue = knapsackGreedy(items, capacity);
cout < "Maximum value in Knapsack = " < maxValue < endl;
return 0;
}
import java.util.Scanner;
import java.util.Arrays;
class Item {
int weight, value;
Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public class KnapsackGreedy {
public static void swap(Item[] items, int i, int j) {
Item temp = items[i];
items[i] = items[j];
items[j] = temp;
}
public static void sortItemsByRatio(Item[] items) {
Arrays.sort(items, (Item a, Item b) -> {
double r1 = (double) a.value / a.weight;
double r2 = (double) b.value / b.weight;
return Double.compare(r2, r1); // Sort in descending order
});
}
public static double knapsackGreedy(Item[] items, int capacity) {
sortItemsByRatio(items);
double totalValue = 0.0;
int currentWeight = 0;
for (Item item : items) {
if (currentWeight + item.weight <= capacity) {
currentWeight += item.weight;
totalValue += item.value;
} else {
int remainingCapacity = capacity - currentWeight;
totalValue += (double) item.value * ((double) remainingCapacity / item.weight);
break;
}
}
return totalValue;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of items: ");
int n = scanner.nextInt();
Item[] items = new Item[n];
for (int i = 0; i < n; i++) {
System.out.printf("Enter value and weight for item %d: ", i + 1);
int value = scanner.nextInt();
int weight = scanner.nextInt();
items[i] = new Item(weight, value);
}
System.out.print("Enter the capacity of the knapsack: ");
int capacity = scanner.nextInt();
double maxValue = knapsackGreedy(items, capacity);
System.out.printf("Maximum value in Knapsack = %.2f\n", maxValue);
scanner.close();
}
}
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
def sort_items_by_ratio(items):
# Sort items by value/weight ratio in descending order
items.sort(key=lambda item: item.value / item.weight, reverse=True)
def knapsack_greedy(items, capacity):
# Sort items by value/weight ratio
sort_items_by_ratio(items)
total_value = 0.0
current_weight = 0
for item in items:
if current_weight + item.weight <= capacity:
current_weight += item.weight
total_value += item.value
else:
remaining_capacity = capacity - current_weight
total_value += item.value * (remaining_capacity / item.weight)
break
return total_value
def main():
n = int(input("Enter the number of items: "))
items = []
for i in range(n):
value, weight = map(int, input(f"Enter value and weight for item {i + 1}: ").split())
items.append(Item(weight, value))
capacity = int(input("Enter the capacity of the knapsack: "))
max_value = knapsack_greedy(items, capacity)
print(f"Maximum value in Knapsack = {max_value:.2f}")
if __name__ == "__main__":
main()
Time Complexity of Fractional Knapsack Problem (Greedy
Approach)
Time Complexity Basic Operation: Sorting and Selection
Analysis
The time complexity of the Fractional Knapsack algorithm is O(n \log n). The most
time-consuming operation is sorting the items based on their value-to-weight ratio, which takes
O(n \log n) time. After sorting, the algorithm iterates through the sorted items,
performing constant-time operations for each item, which takes O(n) time.
Therefore, the overall time complexity of the algorithm is:
T(n) = O(n log n) + O(n) = O(n log n)